import collections
from typing import List


class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:

        def _is_valid(x, y):
            return 0 <= x < m and 0 <= y < n

        # 四个方向传递
        def _get_neighbors(x1, y1):
            return [(x2, y2) for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]
                    if _is_valid(x2, y2)]

        m, n = len(isWater), len(isWater[0])
        ans = [[-1] * n for _ in range(m)]

        queue = collections.deque()

        for i in range(m):
            for j in range(n):
                if isWater[i][j] == 1:
                    ans[i][j] = 0
                    queue.append((i, j))

        now = 1
        while queue:
            for _ in range(len(queue)):
                i1, j1 = queue.popleft()
                for i2, j2 in _get_neighbors(i1, j1):
                    if ans[i2][j2] == -1:
                        ans[i2][j2] = now
                        queue.append((i2, j2))
            now += 1

        return ans


if __name__ == "__main__":
    # [[1,0],[2,1]]
    print(Solution().highestPeak(isWater=[[0, 1], [0, 0]]))

    # [[1,1,0],[0,1,1],[1,2,2]]
    print(Solution().highestPeak(isWater=[[0, 0, 1], [1, 0, 0], [0, 0, 0]]))
